package leetcode.code0106;

import java.util.HashMap;
import java.util.Map;

import leetcode.helper.tree.TreeNode;

public class Solution extends Solution106 {

	private Map<Integer, Integer> map;

	@Override
	public TreeNode buildTree(int[] inorder, int[] postorder) {
		map = new HashMap<>();
		for (int i = 0; i < inorder.length; i++) {
			map.put(inorder[i], i);
		}
		return this.buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
	}

	private TreeNode buildTree(int[] inorder, int LI, int RI, int[] postorder, int LP, int RP) {
		if (LI > RI || LP > RP) {
			return null;
		}
//		中序遍历 inorder = [9,3,15,20,7]
//		后序遍历 postorder = [9,15,7,20,3]
		int val = postorder[RP]; // val == 3
		int index = map.get(val); // index == 1
		int leftSize = index - LI; // leftSize == 1
		TreeNode root = new TreeNode(val);
		// inorder [LI,index-1] == [9] [LP,LP+leftSize-1] [9]
		root.left = this.buildTree(inorder, LI, index - 1, postorder, LP, LP + leftSize - 1);
		// inorder [index + 1, RI] == [15,20,7] [LP + leftSize, RP - 1] [15,7,20]
		root.right = this.buildTree(inorder, index + 1, RI, postorder, LP + leftSize, RP - 1);
		return root;
	}

}
